/* ************************************************************************
> File Name:     1.c
> Author:        zhfu
> mail:          3346897597@qq.com
> Created Time:  2022年04月18日 星期一 10时40分01秒
> Description:   
 ************************************************************************/
#include<stdio.h>
#define MAX_ROW 5
#define MAX_COL 5

int maze[MAX_ROW][MAX_COL] = {
    0, 1, 0, 0, 0,
    0, 1, 0, 1, 0,
    0, 0, 0, 0, 0,
    0, 1, 1, 1, 0,
    0, 0, 0, 1, 0
};

/*创建pointer数据结构来标记经过的点*/
struct pointer
{
    int row;
    int col;
};

/*stack包括6部分，存储空间，栈顶指针，push以及pop操作, 检测为空和是否已满，
 * 这里不会满，所以未检测，但是可能为空，当不可能走出迷宫时，stack最终会为空
 */
struct pointer stack[512];
int head = 0;

void push(struct pointer p)
{
    stack[head++] = p;
}

struct pointer pop()
{
    return stack[--head];
}

int is_empty()
{
    return head == 0;
}

/*创建pre数据结构来标记到达pointer[row][col]时其前驱点是pre[row][col]*/
struct pointer pre[MAX_ROW][MAX_COL] = {
    { {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1} },
    { {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1} },
    { {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1} },
    { {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1} },
    { {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1} },
};

int cnt = 0;/*为了更直观表现每次print_maze，用来标号*/

void print_maze(void)
{
    int i, j;
    printf("-------%d----------\n", cnt++);
    for (i = 0; i < MAX_ROW; ++i){
        for (j = 0; j < MAX_COL; ++j){
            printf("%d ", maze[i][j]);
        }
        putchar('\n');
    }
    printf("*****************\n");
}

void visit(int row, int col, struct pointer pr)
{
    struct pointer p = {row, col}; /*经过了该点*/
    maze[row][col] = 2; /*经过后标记*/
    pre[row][col] = pr; 
    push(p);
}

void print_routine(struct pointer p)
{
    if (p.row == -1) /*利用递归反向打印的边界条件一定是要打印的第一个的上一层，也就是这里我第一个要打印（0, 0），那if的条件就是（0, 0）的前驱点*/
        return;
    struct pointer tmp = pre[p.row][p.col];
    print_routine(tmp);
    printf("(%d, %d)\n", p.row, p.col);
}

int main()
{
    struct pointer p = {0, 0};
    push(p);
    maze[0][0] = 2; /*经过之后设置它值，后续需要检测是否已经经过该点，防止鬼打墙*/

    /*主要以下全部都是if不是if else，因为每次都搜寻可走的所有路径
     *visit函数必须传入前置点，否则visit函数中在未压栈前取栈顶元素作为前置点是错误的，
     *因为每次搜寻并不是只能找到一条路，如果是多条路，此时栈顶的元素就不是前置点
     *每次搜索到一条路，一个循环后（从visit到pop）栈中元素不变，因为push一次pop一次
     *每次搜索到多条路，一个循环后（从visit到pop）栈中元素增加，因为push多次pop一次
     *如果没有搜索到路，则一个循环后减少栈中一个元素，也就是把上次多push的路pop出来，相当于回到上一个岔路
     *if 的顺序会影响每次岔路口的选择，后push的路会优先走，因为后push先pop，所以if选项越靠后的，优先走
     *查看本程序print_maze的输出可知，在第6次之后选择了往上走，之后一直走到死胡同（第9个输出），
     *此时不能进入任何一个if选项，在print_maze（第10个输出）后，将进行pop操作，此时pop出来的就是第6次未选择的岔路，
     *第6次之后走的路由于只有一条路可选，所以并不会改变栈，所以这次的pop出来的是上一次未选择的岔路（第11个输出），然后顺利抵达终点
     */
    while (!is_empty()){ 
        p = pop();
        if (p.row + 1 == MAX_ROW && p.col + 1 == MAX_COL)
            break;
        if (p.row + 1 < MAX_ROW && maze[p.row + 1][p.col] == 0) /*向下边走*/
            visit(p.row + 1, p.col, p); /*共同操作写成函数*/
        if (p.row - 1 >= 0 && maze[p.row - 1][p.col] == 0) /*向上走*/
            visit(p.row - 1, p.col, p);
        if (p.col + 1 < MAX_COL && maze[p.row][p.col + 1] == 0) /*向右走*/
            visit(p.row, p.col + 1, p);
        if (p.col - 1 >= 0 && maze[p.row][p.col - 1] == 0) /*向左走*/
            visit(p.row, p.col - 1, p);
        print_maze();
    }
/*
 * 反向打印路线
    if (p.row + 1 == MAX_ROW && p.col + 1 == MAX_COL){
        printf("(%d, %d)", p.row, p.col);
        while (pre[p.row][p.col].row != -1){
            printf("(%d, %d)", pre[p.row][p.col].row, pre[p.row][p.col].col);
            p = pre[p.row][p.col];
        }
    }
*/
    if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1)
        print_routine(p);

    return 0;
}
